#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <algorithm>
using namespace std;

class Solution 
{
public:
	vector<vector<int> > permuteUnique(vector<int> &num) 
	{
		// Start typing your C/C++ solution below
		// DO NOT write int main() function

		vector<vector<int> > result;
		if(num.empty())
			return result;

		sort(num.begin(),num.end());

		do
		{
			result.push_back(num);
		}while(nextPermutation(num));

		return result;
	}
private:
	bool nextPermutation(vector<int> &num) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		if(num.size()<=1)
			return false;

		size_t count = num.size();
		size_t maxR = -1;
		for(size_t i=0;i<(count-1);i++)
		{
			if(num[i]<num[i+1])
			{
				maxR = i;
			}
		}

		if(maxR == -1)
		{
			return false;
		}
		else
		{
			size_t curR = maxR;
			for(size_t i = maxR+1;i<count;i++)
			{
				if(num[i]<=num[curR])
				{
					maxR = i-1;
					break;
				}
			}

			if(maxR==curR)
				maxR = count-1;

			swap(num[curR],num[maxR]);
			size_t i=curR+1, j = num.size()-1;
			while(i<j)
			{
				swap(num[i],num[j]);
				i++,j--;
			}
		}

		return true;
	}
};
#endif
